package 算法.leetcode.offer;

import java.util.Arrays;

/**
 * @author lchenglong
 * @date 2022/3/21
 */
public class Offer56_I {

    public static void main(String[] args) {
        Offer56_I instance = new Offer56_I();
        int[] nums = new int[]{1,2,10,4,1,4,3,3};
        int[] ans = instance.singleNumbers(nums);
        System.out.println(Arrays.toString(ans));
    }
    public int[] singleNumbers(int[] nums) {
        // 数组所有的数异或运算得到一个异或值
        int ret = 0;
        for (int num : nums){
            ret ^= num;
        }
        // 从右往左找到ret中第一个为1的位，
        int div = 1;
        while ((div&ret) == 0){
            div <<=1;
        }
        // 按照异或值是否为0进行分组，
        // 因为两个数异或为1，那么这一位肯定不相同，所以这两个不同的值肯定在不同的组
        int a=0,b=0;
        for (int i:nums){
            if ((i & div) == 0 ){
                a^=i;
            } else {
                b^=i;
            }
        }
        return new int[]{a,b};
    }
}
